package leetcode.p1728;

/**
 * @author: trtan
 * @create: 2021-02-23 15:25
 * @description:
 **/
public class CatAndMouseII2 {
    public static void main(String[] args) {
        String[] grid = new String[]{".M...","..#..","#..#.","C#.#.","...#F"};
        System.out.println(new CatAndMouseII2().canMouseWin(grid, 3, 1));
    }
    public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
        char[][] rebuildGrid = new char[grid.length][grid[0].length()];
        for (int i = 0; i < grid.length; i++) {
            rebuildGrid[i] = grid[i].toCharArray();
        }
        int[][][][][]state = new int[rebuildGrid.length][rebuildGrid[0].length][rebuildGrid.length][rebuildGrid[0].length][205];
        Point C = null, M = null, F = null;
        for (int i = 0; i < rebuildGrid.length; i++) {
            for (int j = 0; j < rebuildGrid[i].length; j++) {
                if (rebuildGrid[i][j] == 'C') C = new Point(i, j);
                else if (rebuildGrid[i][j] == 'M') M = new Point(i, j);
                else if (rebuildGrid[i][j] == 'F') F = new Point(i, j);
                for (int k = 0; k < rebuildGrid.length; k++) {
                    for (int l = 0; l < rebuildGrid[k].length; l++) {
                        for (int m = 0; m < 205; m++) {
                            state[i][j][k][l][m] = -1;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < rebuildGrid.length; i++) {
            for (int j = 0; j < rebuildGrid[i].length; j++) {
                System.out.print(rebuildGrid[i][j]);
            }
            System.out.println();
        }
        int x = playGameWhoWin(rebuildGrid, state, C, M, 1, catJump, mouseJump);
        return x == 1 ? true : false;
    }

    /**
     * @author trtan
     * @date 2021/2/23 21:05
     * description:
     * @param grid
     * @param state 记忆搜索，记录状态
     * @param C
     * @param M
     * @param step 当前步数
     * @param catJump
     * @param mouseJump
     * @return int
     */
    private int playGameWhoWin(char[][] grid, int[][][][][] state, Point C, Point M, int step, int catJump, int mouseJump) {
//        System.out.println("step: " + step + ", C: " + C.x + ", " + C.y + ", M: " + M.x + ", " + M.y);
        // 猫赢
        if (step > 200) return 0;
        // 当前状态已经走过一遍了，所以直接返回即可
        if (state[C.x][C.y][M.x][M.y][step] != -1) return state[C.x][C.y][M.x][M.y][step];
        // 偶数猫走
        if (step % 2 == 0) {
            // 配置为1，如果猫没有一种情况能赢那就是老鼠赢
            state[C.x][C.y][M.x][M.y][step] = 1;
            // 上下左右四个方向
            for (int i = -catJump; i <= catJump; i++) {
                for (int j = -catJump; j <= catJump; j++) {
                    if (i * j == 0) {
                        int nx = C.x + i;
                        int ny = C.y + j;
                        // 越界
                        if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length) continue;
                        // 在此需要判断该行该列是否有墙阻挡
                        if (checkWall(grid, C.x, C.y, nx, ny)) continue;
                        // 碰到墙
                        if (grid[nx][ny] == '#') continue;
                        // 碰到食物
                        if (grid[nx][ny] == 'F') {
                            state[C.x][C.y][M.x][M.y][step] = 0;
                            return 0;
                        }
                        // 碰到老鼠
                        if (nx == M.x && ny == M.y) {
                            state[C.x][C.y][M.x][M.y][step] = 0;
                            return 0;
                        }
                        // 猫只要有一种情况赢，那就是猫赢
                        if(playGameWhoWin(grid, state, new Point(nx, ny), M, step + 1, catJump, mouseJump) == 0) {
                            state[C.x][C.y][M.x][M.y][step] = 0;
                            return 0;
                        }
                    }
                }
            }
        }
        else {
            // 配置为0，如果老鼠没有一种情况赢那就是猫赢
            state[C.x][C.y][M.x][M.y][step] = 0;
            for (int i = -mouseJump; i <= mouseJump; i++) {
                for (int j = -mouseJump; j <= mouseJump; j++) {
                    if (i * j == 0) {
                        int nx = M.x + i;
                        int ny = M.y + j;
                        // 越界
                        if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length) continue;
                        // 在此需要判断该行该列是否有墙阻挡
                        if  (checkWall(grid, M.x, M.y, nx, ny)) continue;
                        //碰到墙
                        if (grid[nx][ny] == '#') continue;
                        // 碰到猫
                        if (nx == M.x && ny == M.y) continue;
                        // 碰到食物
                        if (grid[nx][ny] == 'F') {
                            state[C.x][C.y][M.x][M.y][step] = 1;
                            return 1;
                        }
                        // 老鼠只要有一种情况赢，即老鼠赢
                        if (playGameWhoWin(grid, state, C, new Point(nx, ny), step + 1, catJump, mouseJump) == 1) {
                            state[C.x][C.y][M.x][M.y][step] = 1;
                            return 1;
                        }
                    }
                }
            }
        }
        return state[C.x][C.y][M.x][M.y][step];
    }

    /**
     * @author trtan
     * @date 2021/2/23 13:38
     * description: 如果两点间有墙return true
     * @param grid
     * @param x
     * @param y
     * @param nx
     * @param ny
     * @return boolean
     */
    private boolean checkWall(char[][] grid, int x, int y, int nx, int ny) {
        int l = Math.min(x, nx);
        int r = Math.max(x, nx);
        for (int i = l; i <= r; i++) {
            if (grid[i][y] == '#') return true;
        }
        l = Math.min(y, ny);
        r = Math.max(y, ny);
        for (int i = l; i <= r; i++) {
            if (grid[x][i] == '#') return true;
        }
        return false;
    }

    private static class Point {
        Integer x, y;
        Point() {}
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}
